package opgave3;

import java.util.ArrayList;
import java.util.Iterator;

public class BinaireZoekboom<E extends Data> implements BinaireZoekboomInterface<E> {
	private Node<E> root;
	
	public BinaireZoekboom() {
		root = null;
	}
	
	public void init() {
		root = null;
	}

	public void add(E data) {
		Node<E> node = new Node<E>(data);
		if(root == null) {
			root = node;
			return;
		}
		Node<E> currentNode = root;
		while(true) {
			int comparison = data.compareTo(currentNode.data);
			if (comparison == 0) {
				return;
			} else if (comparison < 0) {
				if (currentNode.hasLeftChild()) {
					currentNode = currentNode.leftChild;
				} else {
					currentNode.leftChild = node;
					node.parent = currentNode;
					return;
				}
			} else if (comparison > 0) {
				if (currentNode.hasRightChild()) {
					currentNode = currentNode.rightChild;
				} else {
					currentNode.rightChild = node;
					node.parent = currentNode;
					return;
				}
			}
		}
	}
	
	public boolean contains(E data) {
		return contains(root, data);
	}
	
	private boolean contains(Node<E> node, E data) {
		if(node == null) {
			return false;
		}
		int comparison = data.compareTo(node.data);
		if(comparison == 0) {
			return true;
		} else if (comparison < 0) {
			return contains(node.leftChild, data);
		} else {
			return contains(node.rightChild, data);
		}
	}
	
	public void remove(E data) {
		if(data.compareTo(root.data) == 0) {
			root.parent = new Node<E>(null);
			root.parent.leftChild = root;
			root.remove(data);
			root = root.parent.leftChild;
		} else {
			root.remove(data);
		}
	}
	
	public Iterator<E> ascendingIterator() {
		ArrayList<E> result = new ArrayList<E>();
		
		if(root!=null) {
			inOrderAscending(root, result);
		}
		
		return result.iterator();
	}
	
	private void inOrderAscending(Node<E> node, ArrayList<E> result) {
		if (node.hasLeftChild()) {
			inOrderAscending(node.leftChild, result);
		}
		result.add(node.data);
		if (node.hasRightChild()) {
			inOrderAscending(node.rightChild, result);
		}
	}
	
	public Iterator<E> descendingIterator() {
		ArrayList<E> result = new ArrayList<E>();
		
		if(root != null) {
			inOrderDescending(root, result);
		}		
		
		return result.iterator();
	}
	
	private void inOrderDescending(Node<E> node, ArrayList<E> result) {
		if (node.hasRightChild()) {
			inOrderDescending(node.rightChild, result);
		}
		result.add((E)node.data.clone());
		if (node.hasLeftChild()) {
			inOrderDescending(node.leftChild, result);
		}
	}
	
	public BinaireZoekboom<E> clone() {
		BinaireZoekboom<E> result = new BinaireZoekboom<E>();
		
		result.root = root.clone();
		
		Node<E> currentNode = root;
		Node<E> currentCloneNode = result.root;
		
		cloneNodeChildren(currentNode, currentCloneNode);
		
		return result;
	}
	
	private void cloneNodeChildren(Node<E> currentNode, Node<E> currentCloneNode) {
		if(currentNode.hasLeftChild()) {
			currentCloneNode.leftChild = currentNode.leftChild.clone();
			currentCloneNode.leftChild.parent = currentCloneNode;
			cloneNodeChildren(currentNode.leftChild, currentCloneNode.leftChild);
		}
		if(currentNode.hasRightChild()) {
			currentCloneNode.rightChild = currentNode.rightChild.clone();
			currentCloneNode.rightChild.parent = currentCloneNode;
			cloneNodeChildren(currentNode.rightChild, currentCloneNode.rightChild);
		}
	}
}
